package simple;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/12/7 23:31
 */
public class No401_二进制手表 {
    public static void main(String[] args) {
        Solution401 solution401 = new Solution401();
        List<String> stringList = solution401.readBinaryWatch(2);

        System.out.println();

    }
}

class Solution401 {
    //●○
    public List<String> readBinaryWatch(int num) {
        // 二进制,用1代表灯点亮,0代表灯没点亮
        // 0000000000-1111111111 (10个1) 0->1023 i
        //初始化数据
        int[] data = new int[]{8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
        List<String> res = new ArrayList<>();

        if (num == 0) {
            res.add("0:00");
            return res;
        }

        //1.遍历所有灯的状态 0-1023
        for (int i = 0; i < 1024; i++) {
            //2.获取状态中1的个数,如何快速获取?? No191_位1的个数
            if (get1(i) == num) {
                //说明num个灯点亮,可以计算时间
                //3.当1的个数=num,开始获取1的位置
                //4.根据位置获取时间,剔除无效时间
                String time = getTime(data, i);
                //time:-6666无效
                if (!time.equals("-6666")) {
                    //加入
                    //是否存在重复问题???
                    res.add(time);
                }
            }
        }
        //5.扔入res:List<String> 大功告成!
        return res;
    }

    //i代表状态,有几个1代表几个灯亮
    public String getTime(int[] data, int i) {
        //获取1的位置,根据1的位置计算时间
        //获取1的位置
        //不正经算法!

        int hourSum = 0;
        int minuteSum = 0;

        //0001000100
        int index = -39759349;
        while (i != 0) {
            int check = i & (-i); //100 -> 4
            //对数计算;v:用来获取索引
            int v = (int) (Math.log(check) / Math.log(2)); //2
            index = data.length - 1 - v;
            //计算时间
            if (index < 4) {
                hourSum += data[index];
            } else {
                minuteSum += data[index];
            }

            i = i - check;//这段注意理解,为了获取下一级的1
        }

        //时间有效性判断
        if (hourSum > 11 | minuteSum > 59) {
            return "-6666";
        }

        //补0判断
        if (minuteSum < 10) {
            return hourSum + ":0" + minuteSum;
        } else {
            return hourSum + ":" + minuteSum;
        }
    }

    // 如果不明白:移步至No191视频有详细介绍
    public int get1(int n) {
        //二进制位运算(模拟十进制加减)
        n = ((n & 0x55555555)) + ((n >> 1) & 0x55555555); // 0101
        n = ((n & 0x33333333)) + ((n >> 2) & 0x33333333); // 0011
        n = ((n & 0x0f0f0f0f)) + ((n >> 4) & 0x0f0f0f0f); // 00001111
        n = ((n & 0x00ff00ff)) + ((n >> 8) & 0x00ff00ff); // 0000000011111111
        n = ((n & 0x0000ffff)) + ((n >> 16) & 0x0000ffff); // 0101
        return n;
    }
}



    //public List<String> readBinaryWatch(int num) {
    //    //暴力法!!!!
    //
    //    //1.stack初始化
    //    //2.pop的元素进行处理
    //    //3.pop的处理元素添加栈
    //    //4.栈的时间转换
    //    //5.去重
    //    //6.结果输出
    //
    //    //stack存放灯号组合,即索引
    //    Stack<List<Integer>> stack = new Stack<>();
    //    //(时间,个数)
    //    Map<String, Integer> map = new HashMap<>();
    //    List<String> res = new ArrayList<>();
    //    if (num == 0) {
    //        res.add("0:00");
    //        return res;
    //    }
    //
    //    //1.stack初始化
    //    //所有的灯
    //    int[] data = new int[]{8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
    //    for (int i = 0; i < data.length; i++) {
    //        //新建list
    //        List<Integer> list = new ArrayList<>();
    //        list.add(i);
    //        stack.push(list);
    //    }
    //
    //
    //    //常规二叉树stack模板套用
    //    while (!stack.isEmpty()) {
    //        List<Integer> check = stack.pop();//list(7)
    //        //优化
    //        //每次check出来对时间进行保存,如果遇到相同的,整个树干掉
    //        //时间处理
    //        String time = getT(check, data);
    //        if (map.get(time) == null) {
    //            map.put(time, 1);
    //        }else {
    //            continue;
    //        }
    //        //不可以处理时间
    //        if (check.size() != num) {
    //            //pop的处理元素添加栈
    //            for (int i = 0; i < data.length; i++) {
    //                if (!check.contains(i)) {
    //                    //不包含才加入
    //                    //不能对check进行操作
    //                    List<Integer> list = new ArrayList<>();
    //                    //基于check
    //                    list.addAll(check);
    //                    list.add(i);
    //
    //                    //栈推入
    //                    stack.push(list);
    //                }
    //            }
    //        } else {
    //            //无效时间不加入
    //            if (!"-6666".equals(time)) {
    //                //有效
    //                res.add(time);
    //            }
    //        }
    //
    //    }
    //    //4.栈的时间转换
    //    //对list里面的元素操作->时间字符串
    //    return res;
    //}
    //
    ////对list里面的元素操作->时间字符串
    ////list:点亮的灯组合
    ////data:对应灯的时间
    //public String getT(List<Integer> list, int[] data) {
    //    //list(0,1,2,3) -> 15:00??
    //    //list(0,7,8) -> 8:06
    //
    //    int hourSum = 0;
    //    int minuteSum = 0;
    //    //对索引操作
    //    for (int shijian : list) {
    //        //注意越界问题
    //        //0-11:0-59??
    //        if (shijian < 4) {
    //            hourSum += data[shijian];
    //        } else {
    //            minuteSum += data[shijian];
    //        }
    //    }
    //
    //    //0-11,0-59合法
    //    if (hourSum > 11 || minuteSum > 59) {
    //        //非法
    //        return "-6666";
    //    }
    //
    //    //分钟问题:小于10,补0
    //    if (minuteSum < 10) {
    //        return hourSum + ":0" + minuteSum;
    //    } else {
    //        return hourSum + ":" + minuteSum;
    //    }
    //}
    //
    ////去重重要方法
    //public void addMapKeys(Map<String, Integer> map, String key) {
    //    if (map.get(key) == null) {
    //        map.put(key, 1);
    //    } else {
    //        map.put(key, map.get(key) + 1);
    //    }
    //}


